The present invention relates to error correction in coding schemes for digital communication systems, and more particularly to design optimization for Interleavers of any size, which can be completely specified using only a few design parameters (i.e. a parameterized interleaver).
In communication systems, system performance is aided by error control codes. Nearly all communications systems rely on some form of error control for managing errors that may occur due to noise and other factors during transmission of information through a communication channel. These communications systems can include satellite systems, fiber-optic systems, cellular systems, and radio and television broadcasting systems. Efficient error control schemes implemented at the transmitting end of these communications systems have the capacity to enable the transmission of data including audio, video, text, etc. with very low error rates within a given signal-to-noise ratio (SNR) environment. Powerful error control schemes also enable a communications system to achieve target error performance rates in environments with very low SNR, such as in satellite and other wireless systems where noise is prevalent and high levels of transmission power are costly, if even feasible.
Thus, broad classes of powerful error control schemes that enable reliable transmission of information have emerged including convolutional codes, low density parity check (LDPC) codes, and turbo codes. Both LDPC codes as well as some classes of turbo codes have been successfully demonstrated to approach near the theoretical bound (i.e., Shannon limit). Although long constraint length convolutional codes can also approach the Shannon limit, decoder design complexity prevents practical, wide spread adoption. LDPC codes and turbo codes, on the other hand, can achieve low error rates with lower complexity decoders.
In frequency division multiplexed (FDM) systems, adjacent channel interference (ACI) can seriously impair performance especially when high bandwidth efficiencies are desired. This is because in order to achieve high bandwidth/spectral efficiencies, the frequency separation between the adjacent channels (carriers) must be reduced, causing an increase in ACI and resulting in performance degradation. The performance can be improved by applying interference cancellation at the receiver. Such a design, however, entails an increase in the complexity. Alternatively, the performance could also be improved through a more judicious choice of the modulation and channel (error correction) coding. Bandwidth efficiency can be obtained by choosing modulations such as continuous phase modulation (CPM). Through a careful design of the CPM pulse shape and selection of the remaining modulation parameters, such as the alphabet size M and modulation index h, the power spectrum can be shaped to improve the resilience to ACI.
A pragmatic approach for attempting to achieve energy efficient communication would be the concatenation of a small constraint length binary error correction code and the modulator using a bit interleaver and the application of the “turbo-principle” of iterating between the demodulator and decoder at the receiver. Interleaving is a process of reordering a sequence of symbols or bits in a predetermined manner. “Interleaver size” is equal to the size of the sequence. The apparatus performing the interleaving is referred to herein as an Interleaver. A Turbo Interleaver serves to reorder an input data sequence in a pseudo-random fashion prior to an encoding by a second of the constituent codes. This approach is commonly known as bit interleaved coded modulation with iterative decoding (BICM-ID). The primary goals for error coding (FEC) and interleaver design are flexibility, effective performance, complexity (e.g., implementation complexity) and scalability.
A main problem in such communication systems, however, is an early occurrence of the error floor along the curve of error rate (e.g., frame error rate) with respect to signal to noise ratio. As the signal to noise ratio is improved the frame error rate generally improves in a relative fashion. Particularly, at higher frame error rates, the error rate improves at a sharper slope with respect to improvement in the signal to noise ratio (along the curve of frame error rate with respect to signal to noise ratio), and then at some point, the slop or rate of improvement in the frame error rate drops off or flattens out at lower frame error rates (also known as error floors). This phenomenon is dominated by the interleaver design. The goal of the interleaver design is to prevent early error floors—in other words, the goal is to set the point at which the frame error rate improvement drops off at a lowest practical error rate (e.g., at frame error rates of 10−5 or 10−6).
Coded systems employing small constraint length binary convolutional codes in a BICM-ID framework have been shown to have very good convergence thresholds, and hence perform very well in the waterfall region of the error rate curve. To prevent the early error floors that typically occur in these systems, an S-random bit interleaver is often used between the convolutional encoder and the modulator. The underlying principle behind S-random interleavers is to avoid mapping neighbor positions of an original input sequence to another neighbor position of the interleaved sequence within a window of size S. The design goal in S-random interleavers is to maximize S while preserving the above principle.
S-random interleavers, however, suffer from a main drawback in that they lack a general rule that can be used to specify an interleaver of any size N. A designer, therefore, has no practical option other than creating an explicit listing or specification for the entire interleaver for a given N. Also, S-random interleavers have to be redesigned every time the interleaver size is changed, and there is typically no requirement of any resemblance between the interleavers with similar sizes. Further, specification of the entire interleaver requires a respective amount of memory storage for each interleaver, and the specification of multiple interleavers of differing sizes multiplies the memory requirements. Accordingly, the memory required to store the entire interleaver generally renders the S-random interleaver as an impractical option for use in communication systems in which the interleaver length spans a wide range of values, for instance, from a few hundred bits to several thousand bits.
It is, therefore, desirable to have a general interleaver design based on an interleaver design rule that concisely defines interleavers of any size, which can be completely specified using only a few design parameters (i.e. a parameterized interleaver).